package algorithm_demo.demo05;

/**
 * 假设有排成一行的N个位置，记为1-N，N一定大于或等于2
 * 开始时机器人在其中的M位置上（M一定是1-N中的一个）
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到N-1位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走K步，最终能来到P位置（P也是1-N中的一个）的方法有多少中
 * 给定四个参数N、M、K、P，返回方法数
 *
 * @author Api
 * @date 2023/3/12 11:07
 */
public class Code10_RobotWalk2 {
    public static int way1(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        return process1(N, M, K, P);
    }
    /*暴力递归*/

    /**
     * 递归函数
     *
     * @param N    1-N
     * @param cur  当前位置
     * @param rest 剩余步数
     * @param P    目标位置
     * @return
     */
    public static int process1(int N, int cur, int rest, int P) {
        //base case
        if (rest == 0) {
            return cur == P ? 1 : 0;
        }
        //第一个位置
        if (cur == 1) {
            return process1(N, cur + 1, rest - 1, P);
        }
        //最后位置
        if (cur == N) {
            return process1(N, cur - 1, rest - 1, P);
        }
        //中间位置
        return process1(N, cur + 1, rest - 1, P) + process1(N, cur - 1, rest - 1, P);
    }

    /*暴力递归转动态规划 记忆性搜索*/
    public static int way2(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        /*动态参数*/
        int[][] dp = new int[N + 1][K + 1];
        return process2(N, M, K, P, dp);
    }

    public static int process2(int N, int cur, int rest, int P, int[][] dp) {
        //base case
        if (rest == 0) {
            dp[cur][rest] = cur == P ? 1 : 0;
            return dp[cur][rest];
        }
        //第一个位置
        if (cur == 1) {
            dp[cur][rest] = process1(N, cur + 1, rest - 1, P);
            return dp[cur][rest];
        }
        //最后位置
        if (cur == N) {
            dp[cur][rest] = process1(N, cur - 1, rest - 1, P);
            return dp[cur][rest];
        }
        //中间位置
        dp[cur][rest] = process1(N, cur + 1, rest - 1, P) + process1(N, cur - 1, rest - 1, P);
        return dp[cur][rest];
    }


    /*经典动态规划*/
    public static int way3(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        /*动态参数*/
        int[][] dp = new int[N + 1][K + 1];
        return process3(N, M, K, P, dp);
    }

    public static int process3(int N, int M, int K, int P, int[][] dp) {
        //记录当前P的位置
        dp[P][0] = 1;
        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            //中间位置
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur + 1][rest - 1] + dp[cur - 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[M][K];
    }


    public static void main(String[] args) {
        System.out.println(way1(7, 2, 5, 3));
        System.out.println(way2(7, 2, 5, 3));
        System.out.println(way3(7, 2, 5, 3));
    }
}
